package com.example.algorithm.prefixSum;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
 * 子数组大小 至少为 2 ，且
 * 子数组元素总和为 k 的倍数。
 * 如果存在，返回 true ；否则，返回 false 。
 * 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
 * <p>
 * 示例 1：
 * 输入：nums = [23,2,4,6,7], k = 6
 * 输出：true
 * 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
 * <p>
 * 示例 2：
 * 输入：nums = [23,2,6,4,7], k = 6
 * 输出：true
 * 解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
 * 42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
 * <p>
 * 示例 3：
 * 输入：nums = [23,2,6,4,7], k = 13
 * 输出：false
 */
public class Leetcode523_CheckSubarraySum {
    public static void main(String[] args) {
        int[] nums = {23, 2, 6, 4, 7};
        System.out.println(new Solution().checkSubarraySum(nums, 6));

    }

    static class Solution {
        /**
         * 解法三:使用哈希表 存放前缀和对k取余
         *
         * 如果两个数对k取模相等,那么两数之差一定能被k整除
         * 本题由于要至少连续两个元素的和,
         * 因此如果两个前缀和(prefixSums[p] % k) = (prefixSums[q] % k) ,且 p - q  >= 2
         * 则存在子数组元素总和为 k 的倍数。
         *
         * @param nums
         * @param k
         * @return
         */
        public boolean checkSubarraySum3(int[] nums, int k) {
            if (nums == null || nums.length < 2)
                return false;
            // key: 对k取模的余数, v:每个余数第一次出现的下标
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();// 哈希表存储每个余数第一次出现的下标
            map.put(0, -1);// 规定空的前缀的结束下标为 −1，由于空的前缀的元素和为 0，因此在哈希表中存入键值对 (0,-1)
            int r = 0; // 前缀和余数临时变量
            for (int i = 0; i < nums.length; i++) {
                r = (r + nums[i]) % k;
                if (map.containsKey(r)) {
                    int prefixIndex = map.get(r);
                    if (i - prefixIndex >= 2) { // 两个前缀和对k取模相等 且的下标差大于等于
                        return true;
                    }
                }  else {
                    map.put(r, i);
                }
            }
            return false;
        }

        /**
         * 暴力法(优化)
         * 使用数组记录前缀和
         *
         * @param nums
         * @param k
         * @return
         */
        public boolean checkSubarraySum2(int[] nums, int k) {
            if (nums == null || nums.length == 0)
                return false;
            int[] prefixSums = new int[nums.length];
            // 计算前缀和
            prefixSums[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                prefixSums[i] = prefixSums[i - 1] + nums[i];
            }

            for (int start = 0; start < nums.length - 1; start++) {
                for (int end = start + 1; end < nums.length; end++) {
                    //求第 i 个数到第 j 个数，可以根据前缀和得出为 sum[j] - sum[i] + nums[i]
                    int summ = prefixSums[end] - prefixSums[start] + nums[start];
                    if (k != 0 && summ % k == 0)
                        return true;
                }
            }
            return false;
        }

        /**
         * 暴力法
         * 枚举每个连续的子序列，判断是否存在和是k的整倍数
         *
         * @param nums
         * @param k
         * @return
         */
        public boolean checkSubarraySum1(int[] nums, int k) {

            // 考虑所有长度大于2的子序列之和,然后判断是否能被k整除
            // 方式一:
//            for (int subArrayLen = 2; subArrayLen <= nums.length; subArrayLen++) {
//                for (int i = 0; i < nums.length; i++) {
//                    int sum = 0;
//                    for (int j = i; j < (i + subArrayLen) && (i + subArrayLen <= nums.length); j++) {
//                        sum += nums[j];
//                    }
//
//                    if (sum != 0 && (sum % k == 0)) {
//                        return true;
//                    }
//                }
//            }

            // 方式二:
            for (int start = 0; start < nums.length - 1; start++) { // 子序列开始位置
                for (int end = start + 1; end < nums.length; end++) {// 子序列结束位置
                    int sum = 0;
                    for (int i = start; i <= end; i++)
                        sum += nums[i];

                    if (k != 0 && sum % k == 0)
                        return true;
                }
            }
            return false;

        }

        public boolean checkSubarraySum(int[] nums, int k) {
            return checkSubarraySum1(nums, k);
        }
    }
}
